/*
 * 快速排序算法实现
 * 包含多种pivot选择策略
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "quick_sort.h"

// 交换两个整数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数 - 使用最后一个元素作为pivot
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);      // 小于pivot区域的边界索引

    // 遍历数组，将小于等于pivot的元素放到左边
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;  // 扩展小于pivot的区域
            swap(&arr[i], &arr[j]);
        }
    }
    // 将pivot放到正确的位置
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 分区函数 - 使用随机元素作为pivot
int partition_random(int arr[], int low, int high) {
    // 初始化随机数生成器
    static int initialized = 0;
    if (!initialized) {
        srand(time(NULL));
        initialized = 1;
    }
    
    // 生成[low, high]范围内的随机索引
    int random_index = low + rand() % (high - low + 1);
    
    // 将随机选择的元素与最后一个元素交换
    swap(&arr[random_index], &arr[high]);
    
    // 使用标准分区函数
    return partition(arr, low, high);
}

// 快速排序主函数
// 参数: use_random - 1使用随机pivot, 0使用最后一个元素作为pivot
void quick_sort(int arr[], int low, int high, int use_random) {
    if (low < high) {
        int pi;
        // 根据选择的策略进行分区
        if (use_random) {
            pi = partition_random(arr, low, high);
        } else {
            pi = partition(arr, low, high);
        }

        // 递归排序pivot左右的子数组
        quick_sort(arr, low, pi - 1, use_random);  // 排序左半部分
        quick_sort(arr, pi + 1, high, use_random); // 排序右半部分
    }
}

// 打印数组元素
void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
